package com.mccken.practice.top100.Top_1$20.top_5;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2023-12-30 10:44
 **/
public class ThreeSum {

	// 3 <= nums.length <= 3000
	public List<List<Integer>> threeSum(int[] nums) {
		int len = nums.length;
		Arrays.sort(nums);
		if (nums[0] > 0 || nums[len - 1] < 0) {
			return new ArrayList<>();
		}
		List<List<Integer>> result = new ArrayList<>();

		// 固定nums[i]
		for (int i = 0; i < len; i++) {

			if (i>0 && nums[i] == nums[i-1]) {
				continue;
			}
			
			int right = len - 1;
			int left = i + 1;

			while (right > left) {
				if (left > i + 1 && nums[left] == nums[left - 1]) {
					left++;
					continue;
				}

				if (nums[i] + nums[left] + nums[right] > 0) {
					right--;
				} else if (nums[i] + nums[left] + nums[right] == 0) {
					result.add(Arrays.asList(nums[i], nums[left], nums[right]));
					left++;
					right--;

					while (left < right  && nums[left] == nums[left - 1]) {
						left++;
					}

					while (left < right  && nums[right] == nums[right + 1]) {
						right--;
					}
				} else if (nums[i] + nums[left] + nums[right] < 0) {
					left++;
				}
			}

		}
		return result;
	}

	public List<List<Integer>> threeSum3(int[] nums) {

		int n = nums.length;
		Arrays.sort(nums);

		List<List<Integer>> ans = new ArrayList<>();

		// 枚举a
		for (int first = 0; first < n; first++) {

			if (first > 0 && nums[first] == nums[first - 1]) {
				continue;
			}

			// c指向数组最右端
			int third = n - 1;
			// 负的值
			int target = -nums[first];

			// 枚举b
			for (int second = first + 1; second < n; second++) {
				// 需要和上一次枚举的数不相同
				if (second > first + 1 && nums[second] == nums[second - 1]) {
					continue;
				}

				// 需要保证b的指针在c的指针的左侧
				while (second < third && nums[second] + nums[third] > target) {
					// 移动右侧
					--third;
				}
				// 如果指针重合，随着B后续增加，就不会有满足a+b+c=0，并且b<c的c了，可以退出循环
				if (second == third) {
					break;
				}

				if (nums[second] + nums[third] == target) {
					ans.add(Arrays.asList(nums[first], nums[second], nums[third]));
				}
			}
		}

		return ans;
	}

	public List<List<Integer>> threeSum2(int[] nums) {
		Set<String> set = new HashSet<>();

		// 排序
		Arrays.sort(nums);

		// 特例
		if (nums[0] > 0 || nums[nums.length - 1] < 0) {
			return new ArrayList<>();
		}

		List<List<Integer>> result = new ArrayList<>();
		for (int i = 0; i < nums.length; i++) {
			int r = nums.length - 1;
			int temp_r = r;
			int l = i + 1;

			// 不等于0，让r移动 	
			while (l < r) {

				// 满足条件，加进去
				if (nums[i] + nums[l] + nums[r] == 0) {
					if (set.add(String.valueOf(nums[i]) + nums[l] + nums[r])) {
						result.add(Arrays.asList(nums[i], nums[l], nums[r]));
					}
					r--;
					l = i + 1;
				} else {
					l++;
				}

				while (l < r && r < nums.length - 1 && nums[r] == nums[r + 1]) {
					r--;
				}
				while (l < r && nums[l] == nums[l - 1]) {
					l++;
				}

				if (l >= r) {
					temp_r--;
					r = temp_r;
					l = i + 1;
				}
			}
		}

		return result;

	}

	public List<List<Integer>> threeSum1(int[] nums) {
		// 排序
		Arrays.sort(nums);

		// 特例
		if (nums[0] > 0 || nums[nums.length - 1] < 0) {
			return new ArrayList<>();
		}

		List<List<Integer>> result = new ArrayList<>();
		for (int i = 0; i < nums.length; i++) {
			int r = nums.length - 1;
			int l = i + 1;

			System.out.println(i + ":" + l + ":" + r);
			// 不等于0，让r移动 	
			while (l < r) {

				if (nums[i] == -3 && nums[l] == 1) {
					System.out.println(nums[i] + ":" + nums[l] + ":" + nums[r]);
				}

				// 满足条件，加进去
				if (nums[i] + nums[l] + nums[r] == 0) {
					result.add(Arrays.asList(nums[i], nums[l], nums[r]));
					l++;
					r--;
				} else {
					l++;
				}

				while (l < r && r > nums.length - 1 && nums[r] == nums[r + 1]) {
					r--;
				}
				while (l < r && nums[l] == nums[l - 1]) {
					l++;
				}
			}
		}

		return result;
	}

	/*
	 [[-4,0,4],[-4,1,3],[-3,-1,4],[-3,0,3],[-3,1,2],        [-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]
	 [[-4, 0, 4], [-4, 1, 3], [-3, -1, 4], [-3, 0, 3], [-3, 1, 2]]
	 */

	public static void main(String[] args) {
		ThreeSum o = new ThreeSum();
//		int[] nums = {-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4};
		int[] nums = {-1, 0, 1, 2, -1, -4};
		System.out.println(o.threeSum(nums));

	}

}
